﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace CatEars.Core.Collections
{
    /// <summary>
    /// 内部结构为 List[List[T]] 避免连续内存不足
    /// </summary>
    [DebuggerDisplay("Count={Count} SubCapacity={SubCapacity}")]
    public class List2<T> : IList<T>, ICollection<T>, IEnumerable<T>, IEnumerable
    {
        /// <summary>
        /// 子容器容量
        /// </summary>
        private int m_intSubCapacity = 32;
        /// <summary>
        /// 子容器容量
        /// </summary>
        public int SubCapacity { get { return m_intSubCapacity; } }
        /// <summary>
        /// 内部数据集合
        /// </summary>
        List<List<T>> m_innerList = null;

        /// <summary>
        /// 创建一个默认的List2对象 SubCapacity=2048
        /// </summary>
        public List2() : this(0, 0){ }

        /// <summary>
        /// 指定子容器容量
        /// </summary>
        /// <param name="intSubCapacity">子容器容量</param>
        public List2(int intSubCapacity)
            : this(intSubCapacity, 0)
        {
        }

        /// <summary>
        /// 指定容量
        /// </summary>
        /// <param name="intSubCapacity">子容器容量 传0时候指定为2048</param>
        /// <param name="intTotalCapacity">新列表最初可以存储的元素数</param>
        public List2(int intSubCapacity, int intTotalCapacity)
        {
            if (intSubCapacity == 0)
            {
                //传0时候指定为2048
                intSubCapacity = 2048;
            }
            if (intSubCapacity > 0)
            {
                while (m_intSubCapacity < intSubCapacity)
                {
                    m_intSubCapacity *= 2;
                }
            }
            if (intTotalCapacity > 0)
            {
                m_innerList = new List<List<T>>((intTotalCapacity - 1) / m_intSubCapacity + 1);
            }
            else
            {
                m_innerList = new List<List<T>>();
            }
            //一开始不需要创建对象
            //m_innerList.Add(new List<T>(SubCapacity));
        }

        /// <summary>
        /// 根据大索引计算小索引
        /// </summary>
        /// <param name="intIndex">intIndex</param>
        /// <param name="intIndexMain">intIndexMain</param>
        /// <param name="intIndexSub">intIndexSub</param>
        private void GetIndex(int intIndex,
            out int intIndexMain,
            out int intIndexSub)
        {
            intIndexMain = intIndex / SubCapacity;
            intIndexSub = intIndex % SubCapacity;
        }

        /// <summary>
        /// 根据index取对象
        /// </summary>
        /// <param name="intIndex">索引</param>
        /// <returns>对象</returns>
        public T this[int intIndex]
        {
            get
            {
                int intIndexMain;
                int intIndexSub ;
                GetIndex(intIndex, out intIndexMain, out intIndexSub);
                return m_innerList[intIndexMain][intIndexSub];
            }
            set
            {
                int intIndexMain;
                int intIndexSub;
                GetIndex(intIndex, out intIndexMain, out intIndexSub);
                m_innerList[intIndexMain][intIndexSub] = value;
            }
        }

        /// <summary>
        /// 添加对象到集合
        /// </summary>
        /// <param name="item">item</param>
        public void Add(T item)
        {
            if (m_innerList.Count == 0) m_innerList.Add(new List<T>(SubCapacity));
            var subList = m_innerList[m_innerList.Count - 1];
            if (subList.Count + 1 <= SubCapacity)
            {
                subList.Add(item);
            }
            else
            {
                subList = new List<T>(SubCapacity) { item };
                m_innerList.Add(subList);
            }
            m_intCount++;
        }

        /// <summary>
        /// 清除集合
        /// </summary>
        public void Clear()
        {
            var oldList = m_innerList;
            m_innerList.Add(new List<T>(SubCapacity));
            m_intCount = 0;
            foreach (var subList in oldList)
            {
                subList.Clear();
            }
            oldList.Clear();
        }

        /// <summary>
        /// 集合计数
        /// </summary>
        private int m_intCount = 0;
        /// <summary>
        /// 集合计数
        /// </summary>
        public int Count { get { return m_intCount; } }

        #region IList<T> 成员

#pragma warning disable 1591
        public int IndexOf(T item)
        {
            int intOffset = 0;
            foreach (var coll in m_innerList)
            {
                int intIndex = coll.IndexOf(item);
                if (intIndex >= 0) return intIndex + intOffset;
                else intOffset += coll.Count;
            }
            return -1;
        }

#pragma warning disable 1591
        public void Insert(int intIndex, T item)
        {
            if (intIndex == this.Count)
            {
                Add(item);
                return;
            }
            if (intIndex < 0 || intIndex >= this.Count) throw new IndexOutOfRangeException();
            int intIndexMain;
            int intIndexSub;
            GetIndex(intIndex, out intIndexMain, out intIndexSub);
            var subList = m_innerList[intIndexMain];
            if (subList.Count < SubCapacity)
            {
                subList.Insert(intIndexSub, item);
            }
            else
            {
                var last = subList[SubCapacity - 1];
                subList.RemoveAt(SubCapacity - 1);
                subList.Insert(intIndexSub, item);
                for (int i = intIndexMain + 1; i < m_innerList.Count; i++)
                {
                    var subList0 = m_innerList[i];
                    if (subList.Count < SubCapacity)
                    {
                        subList0.Insert(0, last);
                        m_intCount++;
                        return;
                    }
                    else
                    {
                        var last0 = subList0[SubCapacity - 1];
                        subList0.RemoveAt(SubCapacity - 1);
                        subList0.Insert(0, last);
                        last = last0;
                    }
                }
                this.Add(last);
                m_intCount++;
            }
        }

#pragma warning disable 1591
        public void RemoveAt(int intIndex)
        {
            if (intIndex < 0 || intIndex >= this.Count) throw new IndexOutOfRangeException();

            int intIndexMain;
            int intIndexSub;
            GetIndex(intIndex, out intIndexMain, out intIndexSub);
            var subList = m_innerList[intIndexMain];
            if (subList.Count < SubCapacity)
            {
                subList.RemoveAt(intIndexSub);
            }
            else
            {
                subList.RemoveAt(intIndexSub);
                for (int i = intIndexMain + 1; i < m_innerList.Count; i++)
                {
                    var subList0 = m_innerList[i];
                    var item = subList0[0];
                    subList0.RemoveAt(0);
                    subList.Add(item);
                    subList = subList0;
                }
            }
            if (subList.Count == 0)
            {
                m_innerList.RemoveAt(m_innerList.Count - 1);
            }
            m_intCount--;
        }

        #endregion

        #region ICollection<T> 成员

#pragma warning disable 1591
        public bool Contains(T item)
        {
            foreach (var coll in m_innerList)
            {
                if (coll.Contains(item)) return true;
            }
            return false;
        }

#pragma warning disable 1591
        public void CopyTo(T[] array, int intArrayIndex)
        {
            int intIndex = 0;
            foreach (var coll in m_innerList)
            {
                foreach (var item in coll)
                {
                    array[intIndex + intArrayIndex] = item;
                    intIndex++;
                }
            }
        }

        /// <summary>
        /// 是否只读
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

#pragma warning disable 1591
        public bool Remove(T item)
        {
            int intIndex = IndexOf(item);
            if (intIndex >= 0)
            {
                RemoveAt(intIndex);
                return true;
            }
            return false;
        }

        #endregion

        #region IEnumerable<T> 成员

        /// <summary>
        /// 获取迭代器
        /// </summary>
        /// <returns></returns>
        public IEnumerator<T> GetEnumerator()
        {
            return new List2Enumerator<T>(this);
        }

        #endregion

        #region IEnumerable 成员

        /// <summary>
        /// 获取迭代器
        /// </summary>
        /// <returns></returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        #endregion

        /// <summary>
        /// List2专用迭代器
        /// </summary>
        private class List2Enumerator<T2> : IEnumerator<T2>
        {
            /// <summary>
            /// 总索引
            /// </summary>
            int m_intIndex;
            /// <summary>
            /// 主索引
            /// </summary>
            int m_intMainIndex;
            /// <summary>
            /// 子索引
            /// </summary>
            int m_intSubIndex;
            /// <summary>
            /// 列表
            /// </summary>
            List2<T2> m_list;
            /// <summary>
            /// 初始化List2专用迭代器
            /// </summary>
            /// <param name="list">list</param>
            public List2Enumerator(List2<T2> list)
            {
                m_list = list;
                Reset();
            }

            #region IEnumerator<T> 成员

            /// <summary>
            /// 当前迭代的对象
            /// </summary>
            public T2 Current
            {
                get
                {
                    if (m_intIndex < m_list.Count)
                    {
                        return m_list.m_innerList[m_intMainIndex][m_intSubIndex];
                    }
                    else
                    {
                        return default(T2);
                    }
                }
            }

            #endregion

            #region IDisposable 成员

            /// <summary>
            /// Dispose
            /// </summary>
            public void Dispose()
            {
            }

            #endregion

            #region IEnumerator 成员

            /// <summary>
            /// Current
            /// </summary>
            object IEnumerator.Current
            {
                get { return Current; }
            }

            /// <summary>
            /// 下一个
            /// </summary>
            /// <returns></returns>
            public bool MoveNext()
            {
                m_intIndex++;
                m_intSubIndex++;
                if (m_intSubIndex >= m_list.SubCapacity)
                {
                    m_intSubIndex = 0;
                    m_intMainIndex++;
                }
                return m_intIndex < m_list.Count;
            }

            /// <summary>
            /// 重置
            /// </summary>
            public void Reset()
            {
                m_intIndex = -1;
                m_intMainIndex = 0;
                m_intSubIndex = -1;
            }

            #endregion
        }
    }
}
